\section{Fractional BBC Definition} \label{sec:fbbc_def}

An FBBC game is specified by the same tuple as general BBC games, $\langle V, \prefnoargs, \costnoargs,\budgetnoargs\rangle$, and the
length function $\lengthonearg{u}$ for each $u \in V$. The definition of these sets and functions is the same as in the integral case. The set of nodes is represented by $V$. The affinity function is $w: V \times V \rightarrow \mathbb{Z}$, where $w(u, v)$ indicates $u$'s affinity for $v$. We also have a cost function $c : V \times V \rightarrow \mathbb{Z}$, where $f * c(u,v)$ is the cost to node $u$ for purchasing fraction $f$ of edge $(u,v)$ and a budget function $b : V \rightarrow \mathbb{Z}$, where $b(u)$ is the budget allowed to node $u$. In the fractional case, a strategy for node $u$ is a weight function $x_u: V \rightarrow
[0,1]$ that $u$ places on each outgoing edge $(u,v): v \in V$ such
that $\sum_{(u,v)} \left( \cost{u}{v} \times x_u(v) \right) \le \budget{u}$.  Let
$X_u$ denote a strategy chosen by node $u$ and let $X = \{X_u: u \in
V\}$ denote the collection of strategies.  The network formed by $X$
is simply the directed, capacitated complete graph $G(X)$, in which
the capacity of the directed edge $(u,v)$ is $x_u(v)$.  The utility of
a node $u$ is given by $- \sum_{v \in V} \affinity{u}{v} \cdot f(u \rightarrow v)$, where $f(u \rightarrow v)$ is the cost of a 1-unit
minimum cost flow from $u$ to $v$, according to the capacities given
by $X$ and the lengths from the perspective of $u$ given by
$\lengthonearg{u}$.  We assume that there is also
always an additional edge between each pair of nodes with cost 0, capacity
$\infty$, and length some large integer $M \gg n\max_{x,u,v}
\length{x}{u}{v}$; we refer to $M$ as the {\em disconnection
penalty}. In other words, if the max flow from $u$ to $v$ is $\alpha <
1$, then $f(u \rightarrow v)$ is the cost of the minimum cost $\alpha$ flow from $u$
to $v$ plus $(1-\alpha) \cdot M$.

\begin{theorem}
Every instance of FBBC has a pure Nash equilibrium.
\end{theorem}

\begin{proof}
A game has a pure Nash equilibrium if the strategy space of each
player is a compact, non-empty, convex space, and the utility function
of each player $u$ is continuous on the strategy space of all players
and quasi-concave in the strategy space of
$u$~\cite[Proposition~20.3]{OsborneRubinstein94}.  \junk{(See, for example,
Proposition 20.3 of Osborne-Rubinstein or the lecture notes of
Maheshwari.)}

The strategy space of each player $u$ is simply the convex polytope
given by $\{\sum_v X_u(v) \le \budget{u}\}$.  It is
clearly compact, non-empty, and convex.

The continuity of the utility function is also clear.  It remains to
prove that the utility function of each player is quasi-concave in the
strategy space of the player.  Since the utility function is merely
the negative of the cost, we will show that the cost of the min-cost
flow is a quasi-convex function.

Consider two strategies $X_u$ and $Y_u$ of the player $u$, given fixed
strategies of all other players.  In other words, we have strategy collections $X$ and $Y$ such that $X_v = Y_v$ for all $v \neq u$. Fix a destination $v$.
Suppose there exists a unit flow $f_x$ from $u$ to $v$ in $G(X)$
and a unit flow $f_y$ from $u$ to $v$ in $G(Y)$.  Given any
$\lambda \in [0,1]$, consider the strategy $Z_u = \lambda X_u + (1 -
\lambda) Y_u$ for player $u$.  We define the unit flow $f_z$ from
$u$ to $v$ as follows.  For any edge $e = (a,b)$, we set
$f_y(e) = \lambda f_x(e) + (1 - \lambda)f_y(e)$.  Since $f_x(e)$ is at
most $x_a(b)$ and $f_y(e)$ is at most $y_a(b)$, $f_z(e)$ is at most
$\lambda x_a(b) + (1 - \lambda)y_a(b) = z_a(b)$.  Furthermore, the cost
of the flow equals
\begin{eqnarray*}
&& \sum_{(a,b)} f_z(a,b) \length{u}{a}{b} \\
& = &  \sum_{(a,b)} \length{u}{a}{b} (\lambda f_x(a,b) + (1 - \lambda) f_y(a,b)) \\ 
& = & \lambda [\mbox{cost of edge $(a,b)$ in $X$}] + (1 - \lambda) [\mbox{cost of edge $(a,b)$ in $Y$}] \\ 
& \le & \max\{\mbox{cost of edge $(a,b)$ in $X$},\mbox{cost of edge $(a,b)$ in $X$}\}.
\end{eqnarray*}
Thus, the cost function with respect to one destination is
quasi-convex.  Since the cost for a player is simply the sum of the
weighted costs with respect to all destinations, the quasi-convexity
of the cost function and, hence, the quasiconcavity of the utility
function follow.  This completes the proof of the theorem.
\end{proof}

For our hardness results, we restrict FBBC games to the universal destination case: where all nodes have affinity 1 for the same single node, $\dest$, and affinity 0 for all other nodes. Hardness for this restricted case naturally implies at least the same hardness for the general game.